package LimitedTimeGame.Day_0227;

/**
 * @author zxc
 * @date 2023/02/27 11:25
 **/

/**
 * 题目 ：递减元素使得数组nums呈现锯齿状
 * 题目详述 ：
 * 给你一个整数数组nums，每次 操作会从中选择一个元素并 将该元素的值减少1。
 * 如果符合下列情况之一，则数组A就是 锯齿数组：
 * 每个偶数索引对应的元素都大于相邻的元素，即A[0] > A[1] < A[2] > A[3] < A[4] > ...
 * 或者，每个奇数索引对应的元素都大于相邻的元素，即A[0] < A[1] > A[2] < A[3] > A[4] < ...
 * 返回将数组nums转换为锯齿数组所需的最小操作次数。
 *
 * 提示：
 * 1 <= nums.length <= 1000
 * 1 <= nums[i] <= 1000
 *
 */
public class MovesToMakeZigzag {
    public static void main(String[] args) {
        System.out.println(movesToMakeZigzag(new int[]{7,4,8,9,7,7,5}));
    }
    /**
     * 思路 ：
     * ===》
     * 由于锯齿数组有其仅有两种情况 ：
     * （1）每个偶数索引对应的元素都大于相邻的元素，即A[0] > A[1] < A[2] > A[3] < A[4] > ...
     * （2）每个奇数索引对应的元素都大于相邻的元素，即A[0] < A[1] > A[2] < A[3] > A[4] < ...
     * ===》即，比较者两种情况的锯齿数组，哪一种锯齿数组需要对于原数组nums的操作更少;
     *
     * @param nums
     * @return
     */
    public static int movesToMakeZigzag(int[] nums) {
        // 克隆数组dp 与数组nums中所有元素是完全相同的;
        int[] dp = nums.clone();
        // 即，每个偶数索引对应的元素都大于相邻元素的情况下，所需要的操作次数;
        int evenNumber = 0;
        // 即，每个奇数索引对应的元素都大于相邻元素的情况下，所需要的操作次数;
        int oddNumber = 0;
        int len = nums.length;
        int temp = 0;
        // 在每个奇数索引对应元素都大于相邻元素情况下，由于每次操作都是对于指定元素减一;
        // 即，是对于当前遍历的元素自身进行减一操作，直至当前元素小于两个相邻元素;
        for(int i = 0 ; i < len ; i += 2){
            temp = 0;
            if(i > 0 && dp[i] >= dp[i - 1]){
                temp = dp[i] - dp[i - 1] + 1;
            }
            if(i < len - 1 && dp[i] >= dp[i + 1]){
                temp = Math.max( temp , dp[i] - dp[i + 1] + 1);
            }
            evenNumber += temp;
            dp[i] -= temp;
        }
        // 在每个偶数索引对应元素都大于自身相邻元素情况下，由于每次操作都是减一;
        // 即，是对于当前遍历元素的相邻两个元素进行减一操作，直至当前元素大于两个相邻元素;
        for(int i = 0 ; i < len ; i += 2){
            temp = 0;
            if(i > 0 && nums[i] <= nums[i - 1]){
                temp = nums[i - 1] - nums[i] + 1;
                nums[i - 1] -= temp;
                oddNumber += temp;
            }
            if(i < len - 1 && nums[i] <= nums[i + 1]){
                temp = nums[i + 1] - nums[i] + 1;
                nums[i + 1] -= temp;
                oddNumber += temp;
            }

        }
        // 获取上述两个情况中的最小值 --- 构成锯齿形数组的最少操作次数;
        return Math.min(oddNumber , evenNumber);
    }
}
